package com.leetcode2;

import java.util.LinkedList;
import java.util.List;

public class Index851loudAndRich {
	int[] answer,visited;
	public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        answer = new int[n];
        visited = new int[n];
		List<Integer>[] graph = buildGraph(richer,n);
		for(int i = 0;i < n;i++) {
			answer[i] = teraver(graph,quiet,i);
		}
		return answer;
    }
	
	
	public int teraver(List<Integer>[] graph,int[] quiet,int v) {
		if(graph[v].isEmpty()) return v;
		if(visited[v] != 0) return visited[v];
		
		int res = v;
		for(int t : graph[v]) {
			int s = teraver(graph,quiet,t);
			res = quiet[res] < quiet[s]? res : s;
		}
		visited[v] = res;
		return res;
	}
	
	public List<Integer>[] buildGraph(int[][] richer,int n){
		List<Integer>[] graph = new LinkedList[n];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new LinkedList<>();
		}
		for(int i = 0;i < richer.length;i++) {
			int rich = richer[i][0],poor = richer[i][1];
			graph[poor].add(rich);
		}
		return graph;
    }
}
